package com.lee9213.demo.tree;

/**
 * @author libo
 * @version 1.0
 * @date 2018/2/28 10:53
 */
public class BinaryTree<T extends Comparable<T>> {

    private TreeNode<T> root;

    public TreeNode<T> getRoot() {
        return root;
    }

    public void setRoot(TreeNode<T> root) {
        this.root = root;
    }

    public void insert(T value) {
        TreeNode<T> newNode = new TreeNode<>(value);
        if (root == null) {
            root = newNode;
        } else {
            TreeNode<T> currentNode = root;
            TreeNode<T> parentNode;
            while (true) {
                parentNode = currentNode;
                int i = newNode.getValue().compareTo(currentNode.getValue());
                if (i < 0) {
                    currentNode = currentNode.getLeftNode();
                    if (currentNode == null) {
                        parentNode.setLeftNode(newNode);
                        return;
                    }
                } else {
                    currentNode = currentNode.getRightNode();
                    if (currentNode == null) {
                        parentNode.setRightNode(newNode);
                        return;
                    }
                }
            }
        }
    }

    public TreeNode<T> search(T value) {
        TreeNode<T> currentNode = root;
        if (currentNode != null) {
            while (currentNode.getValue() != value) {
                int i = currentNode.getValue().compareTo(value);
                if (i > 0) {
                    currentNode = currentNode.getLeftNode();
                } else {
                    currentNode = currentNode.getRightNode();
                }

                if (currentNode == null) {
                    return null;
                }
            }

            if (currentNode.isDelete()) {
                return null;
            } else {
                return currentNode;
            }
        } else {
            return null;
        }
    }

    public void inOrder(TreeNode<T> node) {
        if(node !=null && !node.isDelete()) {
            inOrder(node.getLeftNode());
            System.out.print(node.getValue());
            inOrder(node.getRightNode());
        }
    }

    public void preOrder(TreeNode<T> node) {
        if(node !=null && !node.isDelete()) {
            System.out.print(node.getValue());
            preOrder(node.getLeftNode());
            preOrder(node.getRightNode());
        }
    }

    public void postOrder(TreeNode<T> node) {
        if(node !=null && !node.isDelete()) {
            postOrder(node.getLeftNode());
            postOrder(node.getRightNode());
            System.out.print(node.getValue());
        }
    }

}
